//12月15日版本
//已实现：对于每辆车求出最短路径，在冲突时会重新规划路线

//TODO：是否需要掉头的判断，是否在路口多等一会会更快（or在一开始就规划好这个问题）

//实现逻辑
//思路：每辆车的结构体有id，当前站点，下一站点，到达下一站点的时间这几个特征
//使用优先队列，让到达下一站点的时刻最早的车优先出队
//不使用原先的时间减1的思路原因：优先队列不提供对每一个元素的访问功能
//到达路口的车子，倘若无路可走，那就相当于from该路口到该路口时间花了1s堵车
//全路径规划表flow[N][N]是一个NxN阶方阵，存储了当前每一条道路上的车流量
//而刚好在路口的车辆，基于当前时间，规划下一时刻应该往哪里开不会遇到拥堵
//计算所有车辆的总耗时：在车子到达目的地时，将当前的sum+=time;
//当优先队列里没有车时，说明所有车都到了目的地
/*
//思路（已舍弃）：使用一个int time来记录当前时间，每过一秒time+1，1秒行驶距离为1米
//timerest[M]数组存储每一辆车到达下一点所需时间，若到达目的地，则改为-1
//每过一秒timerest全部减1，将离开道路的车辆所在道路上的车流量减1
//一个数组用来存储车辆在哪一条道路上
//倘若timerest数组某几个元素为0，表示某辆车到达了路口：开始规划下一时刻全路径的规划表
//全路径规划表flow[N][N]是一个NxN阶方阵，存储了当前每一条道路上的车流量
//开始规划的策略：对于还在行驶中或者到达目的的车，就不用考虑了，
//刚好在路口的车辆，time=0，应该优先出队进行计算，因此采用优先队列，
//而刚好在路口的车辆，基于当前时间，规划下一时刻应该往哪里开不会遇到拥堵
//计算所有车辆的总耗时：在车子到达目的地时，将当前的sum+=time;
//当所有车的timerest用完时，程序返回
*/
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

// 只有输入输出时的下标是从1开始的，其余都为从0开始
struct Event {
    int time;  //下一次到达站点的事件发生的时间
    int car_id;//车辆的ID
    int from;  //车辆当前所在的节点
    int to;    //车辆即将到达的节点
    Event(int time,int id,int a,int b):time(time),car_id(id),from(a),to(b){}

    // 重载对于Event的比较操作，使其原本是<的逻辑改为大于
    // 剩余等待时间越短越先出队
    bool operator<(const Event& next) const {
        return this->time > next.time;
    }
};

// Dijkstra算法，用于计算某一辆车的最短路径
vector<int> dijkstra(int N, int start, int end, int** roadlength, int** flow, int** restrictions) {
    //存储从起点到各节点的最短距离，前驱节点，节点是否已被访问
    int *distance=new int[N];
    int *previous=new int[N];
    bool *visited=new bool[N];

    //初始化，如果距离为无穷大，则说明起点和该点不直接连通，该点没有前驱节点
    for (int i = 0; i < N; i++) {
        distance[i] =roadlength[start][i];
        visited[i] = false;
        if (i!=start&&distance[i]<INT_MAX)previous[i]=start;
        else previous[i]=-1;
    }
    visited[start]=true;
    distance[start]=0;

    for (int i=0;i<N-1;i++){
        int min_distance = INT_MAX;
        int stop=start;
        for (int j=0;j<N;j++){
            if (!visited[j] && distance[j]<min_distance){
                min_distance=distance[j];
                stop=j;
            }
        }
        visited[stop]=true;
        for (int k=0;k<N;k++){
            if (!visited[k]&&roadlength[stop][k]<INT_MAX && flow[stop][k]<restrictions[stop][k] && distance[stop]+roadlength[stop][k]<distance[k]){
                distance[k]=distance[stop]+roadlength[stop][k];
                previous[k]=stop;
            }
        }
    }
    
    // 构建最短路径
    vector<int> path;
    int node = end;
    while (node != -1) {
        path.push_back(node);
        node = previous[node];
    }
    reverse(path.begin(), path.end()); // 反转路径，使其从起点到终点

    delete[] distance;
    delete[] previous;
    delete[] visited;
    return path;
}

int main() {
    int N, M;
    cin>>N>>M;

    
    /////TODO：分配路径时不通是否应该设置为INT_MAX
    
    // 动态分配二维数组
    int** roadlength=new int*[N];    // 存储道路长度
    int** restrictions=new int*[N];  // 存储道路的流量限制
    int** cars=new int*[M];          // 存储每辆车的起点和终点

    for (int i=0;i<N;i++) {
        roadlength[i]=new int[N];
        restrictions[i]=new int[N];
    }
    for (int i=0;i<M;i++) {
        cars[i]=new int[2];
    }

    //读取道路长度
    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            cin>>roadlength[i][j];
            if (roadlength[i][j]==0&&i!=j)roadlength[i][j]=INT_MAX; 
            //如果道路长度为0，则距离为无穷大
        }
    }

    //读取道路的流量限制
    for (int i=0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    //读取每辆车的起点和终点
    for (int i=0;i<M;i++) {
        cin>>cars[i][0]>>cars[i][1];
        cars[i][0]--; //将输入的起点和终点转换为从0开始的索引
        cars[i][1]--;
    }

    // 初始化流量矩阵
    int** flow=new int*[N];
    for (int i=0;i<N;i++) {
        flow[i]=new int[N];
        for (int j=0;j<N;j++) {
            flow[i][j]=0; // 初始化流量为0
        }
    }

   
    // 为每辆车找到初始路径，并设置事件
    priority_queue<Event> event_queue;
    vector<vector<int>> paths(M);      // 存储每辆车的路径
    vector<vector<int>> history(M);    // 存储每辆车的历史路径
    vector<int> car_arrival_time(M,-1); // 存储每辆车的到达时间，初始为-1

    for (int i=0;i<M;i++){
        paths[i] = dijkstra(N, cars[i][0], cars[i][1], roadlength, flow, restrictions);
        
        //路径中必定至少有一个end所以路径长度至少为1
        if (paths[i].size()==1){
            //如果无法到达？所有路全都堵了
            //TODO：车辆的时间更新？
            if (paths[i][0]==cars[i][0]){//出发点就是终点
                car_arrival_time[i]=0;
                history[i].push_back(cars[i][0]);
                history[i].push_back(cars[i][0]);
                continue;
            }
            /*else{
                history[i].push_back(cars[i][0]);
                event_queue.push(Event(1,i,cars[i][0],cars[i][0]));//使其延长1s再运行
                continue;
            }*/
        }

        history[i].push_back(cars[i][0]);
        int u = paths[i][0];
        int v = paths[i][1];
        int time = roadlength[u][v];
        //time是这条路还需要走的路程，i是车辆编号，v是车下一站要到的地方
        event_queue.push(Event(time,i,u,v)); // 将车辆移动事件加入队列
        flow[u][v]++; // 更新流量
        flow[v][u]++;

        //从路径中移除起点，因为车辆已经从起点出发
        paths[i].erase(paths[i].begin());//TODO：用双端队列会不会好一点？

    }

    while (!event_queue.empty()){
        int current_time=event_queue.top().time;
        
        vector<Event> current_events;
        //处理所有到达下一站的车辆
        while (!event_queue.empty()&&event_queue.top().time==current_time){
            Event event=event_queue.top();
            current_events.push_back(event);
            event_queue.pop();
            if (event.from!=event.to){//若相等则为在某一个路口堵车的车辆，因此不用继续加
                flow[event.from][event.to]--;
                flow[event.to][event.from]--;
                history[event.car_id].push_back(event.to);//历史记录只保存已经到达的站点
            }
        }
        for (Event event:current_events){
            if (event.to==cars[event.car_id][1]){//表示到达目的地
                car_arrival_time[event.car_id]=current_time;
                //history[event.car_id].push_back(event.to);已经在198行加入了
                
            }else{//重新规划路径
                vector<int> newpath=dijkstra(N, history[event.car_id].back(), cars[event.car_id][1], roadlength, flow, restrictions);
                if (newpath.size()==1){
                //如果无法到达？所有路全都堵了
                    //event_queue.push(Event(1,event.car_id,event.from,event.to));//使其延长1s再运行
                    continue;
                }
                else{//能够到达
                    paths[event.car_id] = newpath;
                    int u = newpath[0];
                    int v = newpath[1];
                    flow[u][v]++; // 更新流量
                    flow[v][u]++;
                    int travel_time = current_time + roadlength[u][v];
                    event_queue.push(Event(travel_time, event.car_id,u,v));
                }
            }
        }
    }
           
       

    // 输出每辆车的行驶路线
    for (int i = 0; i < M; i++) {
        //cout << "Car " << i << " path: ";
        if (history[i][0] != cars[i][0]) cout << cars[i][0] + 1 << " "; // 输出起点
        for (int node : history[i]) {
            cout << node + 1; // 输出路径中的节点
            if (history[i][0] != cars[i][1]) cout << " ";
            else break;
        }

    ///*    // 打印每两个站台之间的距离
        cout << " Distances: ";
        for (int j = 1; j < history[i].size(); j++) {
            int u = history[i][j - 1];
            int v = history[i][j];
            cout << roadlength[u][v] << " ";
        }//*/
        cout << endl;
    }
    
    // 输出总耗时
    int sum = 0;
    for (int i = 0; i < M; i++) {
        sum += car_arrival_time[i];
    }
    //cout << "Total time: " << sum << endl;
    cout<<sum<<endl;
    // 释放内存
    for (int i = 0; i < N; i++) {
        delete[] roadlength[i];
        delete[] restrictions[i];
        delete[] flow[i];
    }
    delete[] roadlength;
    delete[] restrictions;
    delete[] flow;
    for (int i = 0; i < M; i++) {
        delete[] cars[i];
    }
    delete[] cars;

    return 0;
}